// Package day_04_tree preorder_range
// @Title day_04_tree
// @Description  前序遍历一颗二叉树
// @Author  == 琳琳也叫王木木 ==  2021/8/30 16:44
// @Create  2021/8/30 16:44
package day_04_tree

// PreorderTraversal 使用递归实现先序遍历一颗二叉树
func PreorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)
	var process = func(root *TreeNode) {}
	process = func(root *TreeNode) {
		if root == nil {
			return
		}
		ans = append(ans, root.Val)
		process(root.Left)
		process(root.Right)
	}
	process(root)
	return ans
}

// PreorderTraversalStack 使用栈实现 先序遍历一颗二叉树
func PreorderTraversalStack(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	ans := make([]int, 0)         // 初始化一个数组容器用来存放数据
	stack := make([]*TreeNode, 0) // 初始化一个栈
	stack = append(stack, root)   // 先把头指针压栈
	//如果栈不为空，就一直循环
	for len(stack) > 0 {
		root = stack[len(stack)-1] // 弹出一个元素
		stack = stack[:len(stack)-1]
		ans = append(ans, root.Val) // 加入
		if root.Right != nil {
			stack = append(stack, root.Right)
		}
		if root.Left != nil {
			stack = append(stack, root.Left)
		}
	}
	return ans
}
